package leetcode_100;

/**
 *@author 周杨
 *JumpGameII_45 Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.
 *describe: AC 95% 用哨兵记录每次能跳跃的区域  以及最大能跳的地方
 *2018年5月7日 下午3:23:42
 */
public class JumpGameII_45 {

	public static void main(String[] args) {
		JumpGameII_45 test=new JumpGameII_45();
		System.out.println(test.jump(new int[] {2,3,1,1,4}));
		System.out.println(test.jump(new int[] {0}));
		System.out.println(test.jump(new int[] {3,0,3,2,0,1,1}));
		System.out.println(test.jump(new int[] {1,2,3}));


	}
	
	public int jump(int[] nums) {
		if(nums.length==1)
			return 0;
		int max=0;//当前能走的最大距离
		int min=0;//当前能走的最大距离所花的最小步数
		int maxIndex=0;
		boolean flag=false;
		int total;
		int index=0;
		while(!flag) {
			for(int i=index;i<=maxIndex;++i) {//只在该步数范围内判断
				total=i+nums[i];//目前这个坐标能跳的最远距离
				if(total>=nums.length-1){
					flag=true;
				}
				if(total>max) {
					max=total;
				}
			}
			++min;
			index=maxIndex;
			maxIndex=max;
		}
        return min;
    }

}
